3  Lezione 4 - 03-10

• Indici invertiti: per ogni termine salviamo una lista detta posting list di tutti i documenti che contengono il termine
  • Il termine sarà la chiave del dizionario (ordinate alfabeticamente), le liste saranno invece sortate per docID, un numero che viene assegnato ad ogni documento, in modo da rendere le operazioni più efficienti (es. intersezione diventa O(n) invece che O(n^2))
• Indexer steps:
  • Crea le coppie (token modificato, docID)
  • Sorta per termini e poi per docID
  • Multiple entries di un termine vengono unite e creato il dizionario e le posting lists
  • Viene aggiunta l’informazione sulla quantità di documenti in cui compare ogni parola, questa informazione è ridondante (denormalizzazione) ma può essere utile per operazioni successive
  • Nelle implementazioni ad ogni termine e per ogni docID è associata una position list, contenente la posizione del primo carattere del termine
    • Questa info potrebbe essere usata ad esempio come explanation per l’utente finale per spiegare perchè quel documento in particolare viene suggerito e/o rankato in una certa posizione
• Query processing:
  • Cerco la chiave di ricerca e prendo la posting list, ripeto il processo per ogni termine
  • Faccio il merge delle liste in caso di AND, l’unione in caso di OR
  • L’algoritmo di merge usa un approccio two pointer: dato che le liste sono sortate confronto i docID, se sono uguali aggiungo il docID nella risposta e avanzo in entrambe le liste, altrimenti avanzo nella lista con il docID minore

• Problemi dei preprocessing steps:
  • Fase di parsing: dipende dal formato del documento, dal linguaggio usato, dall’encoding dei caratteri
    • Problemi di classificazione, vengono risolti euristicamente
      • Se ci sono tanti “the” nel documento, allora è inglese
      • Lo stesso documento però può contenere lingue diverse
  • Tokenizzazione: come dividere in token le parole in casi particolari?
    • parole composte (“state-of-art”, “San Francisco”)
    • genitivo sassone (“Finland’s capital”), problemi relativi alle lingue in generale
    • date, anche in diverso formato
    • numeri di telefono, anche in diverso formato
    • frasi in lingue come giapponese o cinese, che non hanno spazi e hanno simboli appartenenti a idiomi diversi
    • frasi in lingue che si leggono da destra verso sinistra, eccezion fatta per i numeri
  • Stopwords: il trend è quello di mantenerle e non rimuoverle, dato che esistono ora buone tecniche di compressione, e buone tecniche di ottimizzazione delle query, pertanto il 30% risparmiato di spazio è ininfluente.
    • In alcuni casi ho bisogno delle stopwords (“To be or not to be”, l’intera frase è composta da stopwords)
  • Normalizzazione: normalizzare le parole indicizzate e quelle presenti nella query nella stessa forma (U.S.A deve matchare USA, oppure United States of America)
    • Si definiscono classi di equivalenza, ovvero raggruppamenti di parole sintatticamente diverse (con spazi, con trattini, lowercase, uppercase, accenti, simboli proprietari) ma semanticamente equivalenti
    • Il criterio è come gli utenti scrivono le query per queste parole
    • Tokenizzazione e normalizzazione dipendono dal linguaggio
    • L’alternativa alla normalizzazione è quella di aggiungere tutte le varianti di un termine nel dizionario ed espandere le query effettuate (bambino diventa bambino OR bambina OR …), potenzialmente è più potente ma la query è più complicata, quindi è meno efficiente
    • Un problema più difficile da risolvere è costituito dalla presenza di sinonimi, ovvero termini diversi che hanno lo stesso significato, ed omonimi, ovvero termini uguali che hanno significato differente
      • Da non dimenticare anche il problema dei typo, come gestirli? Ad esempio con la distanza di Levenshtein

Recall: il principale problema del modello booleano è il problema del feast or famine, ovvero, data una query ci possono essere restituiti troppi documenti, ma con una piccola modifica della stessa, potrebbe non essere restituito alcun documento. Per ottenere il giusto numero di risultati questo modello richiede all’utente delle skills avanzate che la maggior parte dell’utenza non possiede.

• Ranked retrieval model: invece di una query formata da token e connettori, la query dell’utente è formata da una o più parole in linguaggio naturale

  • Il sistema ritorna un elenco di documenti ordinati per rilevanza rispetto alla query
  • In questo modo possiamo mostrare solo la top k risultati
  • Il nostro obiettivo è dunque quello di ordinare i documenti della collezione sulla base dell’utilità per l’utente. Per fare ciò si può pensare di assegnare ad ogni documento un valore, diciamo nell’intervallo chiuso [0, 1], che misuri il grado di “match” tra il documento e la query. A questo punto ci occorre un metodo per stabilire e quindi assegnare uno score alla coppia (query, document).

• Coefficiente di Jaccard: indice utilizzato per misurare l’overlap tra due insiemi A e B, che nel nostro caso saranno Q (query) e D (documento): jaccard(Q, D) = \dfrac{|Q \cap D|}{|Q \cup D|}

• Il coefficiente sarà 0 se A \cap B = 0, e 1 se confrontiamo lo stesso insieme

Esempio

Query: ides of march

Documento 1: caesar died in march

Documento 2: the long march

jaccard(Query, D1) = \dfrac{1}{6}

jaccard(Query, D2) = \dfrac{1}{5}

Il documento 2 è più rilevante del documento 1

• Problemi dello Jaccard:
  • Non considera la frequenza dei termini
  • I termini rari sono più informativi dei termini frequenti^1. Questa informazione non viene tenuta in considerazione

^1 Un termine raro è più discriminante di un termine frequente, e permette di rendere efficiente query che li coinvolgono.